package top.retain;

/**
 * @author ivorfan
 * @date 2021/8/22 22:08
 */
public class Traversal {

    public static void main(String[] args) {
        findDiagonalOrder(new int[][]{{1,2,3},{4,5,6},{7,8,9}});
    }
    public static int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        if (m == 0 || n == 0) {
            return new int[0];
        }
        int[] res= new int[m * n];
        int idx = 0;
        int i = 0, j = 0;
        res[idx] = mat[i][j];
        idx++;
        while (true) {
            if (i == m -1 && j == n -1) {
                break;
            }
            // 右走一步，到达右边界向下走
            if (i < m -1 && j == n - 1) {
                System.out.println(i + " " + j);
                i++;
                res[idx] = mat[i][j];
                idx++;
            }
            if (j < n - 1) {
                j++;
                res[idx] = mat[i][j];
                idx++;
            }
            // 左下走
            while (i < m - 1 && j > 0) {
                j--;
                i++;
                res[idx] = mat[i][j];
                idx++;
            }
            // 下走一步,遇到左边界向右走
            if (j < n -1 && i == m - 1) {
                j++;
                res[idx] = mat[i][j];
                idx++;
            }
            if (i < m - 1) {
                i++;
                res[idx] = mat[i][j];
                idx++;
            }
            // 往上走
            while (i > 0 && j < n - 1) {
                i--;
                j++;
                res[idx] = mat[i][j];
                idx++;
                System.out.println(i + " " + j);
            }
        }
        return res;
    }
}
